# -*- coding: utf-8 -*-

'''
@author: 5822 - Duarte Marques & 5955 - João Rosa
@date: 06 de Junho de 2013
@obs: Trabalho de Estruturas de Dados e Algoritmos
      Docente: Prof. Jasnau Caeiro
'''

class quicksort:
	'''
	Classe que contém o algoritmo QuickSort.
	'''

	def __init__(self, A):
		'''
		Metodo onde se inicializam as variaveis para
		serem utilizadas mais tarde.
		Recebe como parametro uma lista "A".
		'''
		self.A = A

	def quicksort(self, A, p, r):
		'''
		Metodo que contem o algoritmo de ordenação 
		Quicksort, e executa-o recursivamente.
		Recebe como parametros uma lista "A", o seu indice 
		inicial "p", e o seu indice final "r".
		'''
		if p < r:
			q = self.partition(self.A, p, r)
			self.quicksort(self.A, p, q-1)
			self.quicksort(self.A, q+1, r)
		return self.A

	def partition(self, A, p, r):
		'''
		Metodo que em conjunto com o anterior faz as 
		trocas de posições para obter a lista ordenada.
		'''
		x = self.A[r]
		i = p - 1
		for j in range(p, r):
			if self.A[j] <= x:
				i = i + 1
				self.A[i], self.A[j] = self.A[j], self.A[i]
		self.A[i+1], self.A[r] = self.A[r], self.A[i+1]
		return i+1


# A = [2,8,7,1,3,5,6,4]

# print A

# g = quicksort(A)
# print g.quicksort(A, 0, len(A)-1)